11723. Сочетания с повторениями

Найдите количество способов разместить n одинаковых объектов по k разным местам, где каждое место может содержать произвольное количество объектов.

Вход. Два натуральных числа k и n (k, n ≤ 100).

Выход. Выведите количество способов размещения объектов по модулю 10⁹ + 7.

Пример входа 1	Пример выхода 1
3 4	15
Пример входа 2	Пример выхода 2
3 2	6

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Эта задача сводится к вычислению числа сочетаний с повторениями, что соответствует решению уравнения:

x₁ + x₂ + ...+ x_k = n,

где

· x_i – количество объектов, размещённых в i-м месте,

· k – количество мест.

· n – общее количество объектов.

Каждое x_i может быть любым неотрицательным целым числом. Количество решений этого уравнения определяется формулой (задача Еолимп 11551): .

Пример

В первом примере (k = 3, n = 4) ответ равен = = 15.

Во втором примере (k = 3, n = 2) ответ равен = = 6.

Реализация алгоритма

Определим константы и массив dp для запоминания значений биномиального коэффициента.

#define MAX 201

#define MOD 1000000007

long long dp[MAX][MAX];

Функция Cnk вычисляет значение биномиального коэффициента по модулю MOD = 10⁹ + 7.

long long Cnk(int n, int k)

{

if (n == k) return 1;

if (k == 0) return 1;

if (dp[n][k] != -1) return dp[n][k];

return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % MOD;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &k, &n);

memset(dp, -1, sizeof(dp));

Вычисляем и выводим ответ .

printf("%lld\n", Cnk(n + k - 1, k - 1));